from heapq import heappush, heappop  # 注：使用heap比PriorityQueue更快

INF = int(1e16)


def dijkstra():
    q = [(0, 1)]
    dis[1] = 0
    while q:
        t, x = heappop(q)  # 取的时候直接弹
        if b[x] == False:
            b[x] = True
            for y, len in graph[x]:
                if dis[x] + len < dis[y]:
                    dis[y] = dis[x] + len
                    heappush(q, (dis[y], y))


n, m = map(int, input().split())
dis = [INF] * (n + 10)
b = [False] * (n + 10)
graph = [[] for _ in range(n + 10)]
for i in range(m):
    x, y, len = map(int, input().split())
    graph[x].append((y, len))
dijkstra()
for i in range(1, n + 1):
    if(dis[i] == INF):
        print("-1", end=" ")
    else:
        print(dis[i], end=" ")
